import java.util.Arrays;
import java.util.PriorityQueue;

public class Algorithm {

    /*
    public static void Merge(int[]arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l, p2 = mid + 1, i = 0;
        while (p1 <=mid && p2 <= r) {
            help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
        }

        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <=r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length;i++) {
            arr[l + i] = help[i];
        }
    }

    public static void process(int[] arr, int l, int r) {
        if (r == l) {
            return;
        }
        int mid = l + ((r - l)>>1);
        process(arr, l, mid);
        process(arr, mid + 1, r);
        Merge(arr, l, mid, r);
    }

    public static void mergeSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }
    */

    /*
    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static int[] partition(int []arr, int l, int r) {
        int less = l - 1;//左边界 -1
        int more = r;//右边界正好
        while (l < more) {//l代表现在位置
            if (arr[l] < arr[r]) {//现在小于基准数，左边界下一个与他交换，左边界扩张，l往后走
               swap(arr,++less,l++);
            } else if(arr[l] > arr[r]) {//大于基准数，右边界下个数与其交换，右边扩张，l不变
                swap(arr,--more,l);
            } else {//基准数不东，放置在中间
                l++;
            }
        }
        swap(arr,more,r);//把之前交换的数字交换回来
        return new int[]{less + 1,more};//返回边界
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r ) {
            swap(arr, l + (int)(Math.random() * (r - l + 1)), r);//中间找一个数与最后一个交换，把交换后的最后一个数当基准
            int[] p = partition(arr, l ,r);//partition排序+找边界
            quickSort(arr, l, p[0] - 1);//边界和自己相等，所以往后（前）走
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
     */

    /*
    public static void heapInsert(int[] arr, int index) {

             while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapifiy(int[] arr, int index, int HeapSize) {
        int left = 2 * index + 1;
        while (left < HeapSize) {
            int largest = left + 1 < HeapSize && arr[left + 1] > arr[left] ?
                                                left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int p, int q) {
        int t = arr[q];
        arr[q] = arr[p];
        arr[p]  = t;
    }

    public static void heapSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int HeapSize = arr.length;
        swap(arr, 0, --HeapSize);
        while (HeapSize > 0) {
            heapifiy(arr, 0,HeapSize);
            swap(arr, 0, --HeapSize);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,3,6,4,5,2,9,8};
        //mergeSort(arr);
        //quickSort(arr);
        heapSort(arr);
        System.out.print(Arrays.toString(arr));
    }

     */

    //public static void main(String[] args) {
        /*
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(1);
        heap.add(2);
        heap.add(3);
        heap.add(5);
        heap.add(4);
        heap.add(10);
        heap.add(6);
        System.out.print(heap.toString());
         */

        /*PriorityQueue<Integer> heap = new PriorityQueue<>();
        int ret = 1;
        for (int i = 1; i < 1364;i++) {
            heap.add(ret * 2);
            heap.add(ret * 3);
            heap.add(ret * 5);
            ret = heap.poll();
            while (heap.contains(ret)) {
                heap.poll();
            }
        }

        System.out.println(ret);
        //System.out.println(Integer.MIN_VALUE);


    */

    /*
    public static int getDigit(int num, int d) {
        return num / (int)(Math.pow(10,d)) % 10;
    }

    public static int maxDigit(int[] arr) {
        int max = Integer.MIN_VALUE;
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }

        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    public static void radixSort(int[] arr, int l, int r, int digit) {
        final int radix = 10;
        int i , j;
        int[] bucket = new int[r - l + 1];
        for (int d = 1; d <= digit; d++) {
            int[] count = new int[10];

            for ( i = l; i <= r ; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for ( i = 1; i < radix;i++) {
                count[i] += count[i - 1];
            }

            for ( i = r; i >= l;i--) {
                j = getDigit(arr[i],d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for( i = l, j = 0;i <=r ;i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    public static void radixSort(int[] arr) {
        radixSort(arr, 0, arr.length - 1,maxDigit(arr));
    }

        public static void main(String[] args) {
            int[] arr = {103,72,66,89,106,57,77,43,88};
            radixSort(arr);
            System.out.println(Arrays.toString(arr));
        }

     */

    public static void main(String[] args) {
        System.out.println("I think today I've learnt a lot!!");
    }
}
